//
// Created by Tan Ke on 2023/12/20.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 这道题不难, 主要是有不同的情况需要考虑清楚:
 * 1. 定义最大元素从左移除的距离为LeftMaxLen;
 * 2. 定义最小元素从左移除的距离为LeftMinLen;
 * 3. 定义最大元素从右移除的距离为RightMaxLen;
 * 4. 定义最小元素从右移除的距离为RightMinLen;
 * 5. 定义数组总长度为TotalLen;
 *
 * 讨论:
 * 1. 如果统一从左移除: 那么所用的操作数为: Max(LeftMaxLen, LeftMinLen);
 * 2. 如果统一从右移除: 那么所用的操作数为: Max(RightMaxLen, RightMinLen);
 * 3. 如果从左移除最大元素, 从右移除最小元素, 那么所用的操作数为:
 *      3.1. [ ... Max, ..., Min ...]:   LeftMaxLen + RightMinLen; (TotalLen - RightMinLen > LeftMaxLen)
 *      3.2. [ ... Min, ...., Max, ...]: LeftMaxLen; (TotalLen - RightMinLen < LeftMaxLen)
 * 4. 如果从左移除最小元素, 从右移除最大元素, 那么所用的操作数为:
 *      4.1. [ ... Min, ..., Max, ...]: LeftMinLen + RightMaxLen; (TotalLen - RightMaxLen > LeftMinLen)
 *      4.2. [ ... Max, ..., Min ...]: LeftMinLen; (TotalLen - RightMaxLen < LeftMinLen)
 *
 * 5. 特别的, 如果TotalLen == 1, 那么返回1;
 */

int minimumDeletions(int* nums, int numsSize)
{
    int result_1 = 0, result_2 = 0, result_3 = 0, result_4 = 0;
    int result = 0;
    int LeftMaxIndex = 0;
    int RightMaxIndex = 0;
    int LeftMinIndex = 0;
    int RightMinIndex = 0;

    int maxIndex = 0;
    int minIndex = 0;
    int maxVal = nums[0];
    int minVal = nums[0];

    if (numsSize == 1) {
        return 1;
    }

    for (int i = 1; i < numsSize; i ++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
            maxIndex = i;
        }
        if (nums[i] < minVal) {
            minVal = nums[i];
            minIndex = i;
        }
    }

    LeftMaxIndex = maxIndex;
    LeftMinIndex = minIndex;
    RightMaxIndex = numsSize - maxIndex - 1;
    RightMinIndex = numsSize - minIndex - 1;

    /* 全部从左边移除 */
    if (LeftMaxIndex > LeftMinIndex) {
        result_1 = LeftMaxIndex + 1;
    } else {
        result_1 = LeftMinIndex + 1;
    }

    /* 全部从右边移除 */
    if (RightMaxIndex > RightMinIndex) {
        result_2 = RightMaxIndex + 1;
    } else {
        result_2 = RightMinIndex + 1;
    }

    /* 从左移除最大元素, 从右移除最小元素 */
    if (numsSize - RightMinIndex - 1 > LeftMaxIndex) {
        result_3 = LeftMaxIndex + 1 + RightMinIndex + 1;
    } else {
        result_3 = LeftMaxIndex + 1;
    }

    /* 从左移除最小元素, 从右移除最大元素 */
    if (numsSize - RightMaxIndex - 1 > LeftMinIndex) {
        result_4 = RightMaxIndex + 1 + LeftMinIndex + 1;
    } else {
        result_4 = LeftMinIndex + 1;
    }

    if (result_1 < result_2) {
        result = result_1;
    } else {
        result = result_2;
    }

    if (result > result_3) {
        result = result_3;
    }

    if (result > result_4) {
        result = result_4;
    }

    return result;
}

int main(void)
{
    int nums[8] = {2, 10, 7, 5, 4, 1, 8, 6};
    printf("%d\n", minimumDeletions(nums, 8));

    int nums1[8] = {0, -4, 19, 1, 8, -2, -3, 5};
    printf("%d\n", minimumDeletions(nums1, 8));

    int nums2[1] = {101};
    printf("%d\n", minimumDeletions(nums2, 1));

    return 0;
}
